/**
 * 146. LRU 缓存
 * https://leetcode-cn.com/problems/lru-cache/
 */

/**
 * @constructor
 * @param {number} key
 * @param {number} value
 */
function DoubleLinkedNode(key, value) {
  this.key = key;
  this.value = value;
  this.previous = null;
  this.next = null;
}

/**
 * @constructor
 * @param {number} capacity
 */
function LRUCache(capacity) {
  this.cache = [];
  this.head = null;
  this.tail = null;
  this.length = 0;
  this.capacity = capacity;
}

/**
 * @param {number} key
 * @return {void}
 */
LRUCache.prototype.update = function update(key) {
  const node = this.cache[key];
  if (node === this.head) return;
  if (node === this.tail) {
    this.tail = this.tail.previous;
    this.tail.next = null;
  } else {
    const { previous, next } = node;
    previous.next = next;
    next.previous = previous;
  }
  node.previous = null;
  node.next = this.head;
  this.head.previous = node;
  this.head = node;
};

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function get(key) {
  if (this.cache[key]) {
    this.update(key);
    return this.cache[key].value;
  }
  return -1;
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function put(key, value) {
  if (this.cache[key]) {
    this.update(key);
    this.cache[key].value = value;
    return;
  }
  if (this.length >= this.capacity) {
    delete this.cache[this.tail.key];
    const node = this.tail.previous;
    this.tail.previous = null;
    if (node) node.next = null;
    this.tail = node;
    if (!this.tail) this.head = null;
    this.length -= 1;
  }
  const node = new DoubleLinkedNode(key, value);
  this.cache[key] = node;
  if (this.head) this.head.previous = node;
  node.next = this.head;
  this.head = node;
  if (!this.tail) this.tail = node;
  this.length += 1;
};

const lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
console.log(lRUCache.get(1) === 1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
console.log(lRUCache.get(2) === -1); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
console.log(lRUCache.get(1) === -1); // 返回 -1 (未找到)
console.log(lRUCache.get(3) === 3); // 返回 3
console.log(lRUCache.get(4) === 4); // 返回 4
